public class Leetcode {
}

//leetcode:1142:最长公共子序列
class Solution1 {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length() , n = text2.length();
        //创建一个dp表，表示0~i区间和0~j区间的最长公共子序列的长度
        int[][] dp = new int[m+1][n+1];
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                //如果此时两个位置对应的字符相等，那么它就是一个公共序列
                //此时的最长公共子序列的长度，就为0~i-1和0~j-1的最长公共子序列的长度加1
                if(text1.charAt(i-1) == text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    //如果不等此时0~i和0~j的最长公共子序列的长度就为0~i和0~j-1这个区间的最长公共子序列长度和0~i-1和0~j这个区间的最长公共子序列长度的最大值
                    dp[i][j] = Math.max(dp[i][j-1] , dp[i-1][j]);
                }
            }
        }
        return dp[m][n];
    }
}

//leetcode:1035:不相交的线
class Solution2 {
    //根据题意让我们求两个数组的值相等，且连线后不能相交的最大连线数
    //其实就换一种说法，让我们去求顺序要不发生改变的最长公共子序列的长度
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int m = nums1.length , n = nums2.length;

        int[][] dp = new int[m+1][n+1];

        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                }else{
                    dp[i][j] = Math.max(dp[i-1][j] , dp[i][j-1]);
                }
            }
        }
        return dp[m][n];
    }
}